🔍 이분 탐색 (Binary Search)

1️⃣ 개념

"정답이 될 수 있는 범위를 반씩 줄여가며 탐색하는 알고리즘"

이분 탐색은

👉 정렬된 배열 또는
👉 정답이 커질수록 조건이 단조롭게 변하는 문제에서 사용합니다.

매번 탐색 범위를 전바으로 줄이기 때문에
시간 복잡도가 매우 빠릅니다.

🧐 직관적인 예시

1 ~ 100 중에서 어떤 숫자를 맞혀야 한다면?

• 50인가?
• 아니면 → 절반만 남김
• 또 중간값 확인
• 반복…

👉 이런 "업 & 다운" 방식이 바로 이분 탐색

2️⃣ 언제 이분 탐색을 쓰는가?

이분 탐색은 단순히 배열에서만 쓰는 게 아닙니다.

✅ 결정 문제 (Decision Problem)

"이 값이 가능해?" / "이 조건을 만족해?"

그리고 조건이 단조성을 가질 때

👉 한 번 가능해지면, 그 이후는 전부 가능

➡️ 최소 / 최대 값을 찾는 문제에서 자주 등장

3️⃣ 핵심 아이디어

이분 탐색의 핵심은 두 부분이다.

🔹 탐색 범위

left ~ right

• 정답이 존재할 수 있는 범위
• 보통 문제 조건의 최솟값 ~ 최대값

🔹 판별 함수

"이 midd 값으로 조건을 만족할 수 있는가?"

• true / false 또는
• 시간 ≤ limit 같은 비교 결과

이 함수가 O(n) 이라도
이분 탐색과 결합하면 전체는 빠름.

4️⃣ 기본 구조

let left = 최소값;
let right = 최대값;
let answer = right;

while (left <= right) {
	let mid = Math.floor((left - right) / 2);

	if (mid가 가능한 경우) {
		answer = mid;	// 정답 후보 저장
		left = mid + 1; // 더 큰 값 탐색
	} eles {
		right = mid - 1; // 더 작은 값 탐색
	}
}

• left <= right: 안전한 패턴

5️⃣ 예시: 공장 생산 최소 시간 문제

여러 대의 기계가 있을 때,
총 N개의 제품을 만들기 위한 최소 시간을 구하라.

📌 문제 설명

• 공장에는 m대의 기계가 있다.
• 각 기계는 하나의 제품을 만드는 데 걸리는 시간이 다르다.
• 모든 기계는 동시에 작업 가능하다.

🧐 예시

machines = [2, 3, 7]
N = 10

• 1번 기계: 2초에 1개
• 2번 기계: 3초에 1개
• 3번 기계: 7초에 1개

🧠 관찰

시간 T가 주어졌을 때:

T초 안에 제품 N개를 만들 수 있는가?

이 질무은 Yes/No로 대답 가능하고 시간이 늘어날수록 항상 만들 수 있는 개수는 증가합니다.

🔍 이분 탐색 적용

function solution(n, machines) {
	let left = 1;

	// 가장 빠른 기계 찾기
	let minMachine = Infinity;
	for (let m of machines) {
		if (m < minMachine) minMachine = m;
	}

	// 최악의 경우: 가장 빠른 기계가 혼자 N개 생산
	let right = minMachine * n;
	let answer = right;

	while (left <= right) {
		let mid = Math.floor((left + right) / 2);
		let count = 0;

		for (let m of machines) {
			count += Math.floor(mid / m);
			if (count >= n) break; // 조기 종료
		}

		if (count >= n) {
			answer = mid;       // 가능 → 정답 후보
			right = mid - 1;    // 더 짧은 시간 탐색
		} else {
			left = mid + 1;     // 시간 부족 → 늘리기
		}
	}

	return answer;
}

🧪 실행 예시

console.log(solution(10, [2, 3, 7])); // ✅ 12

• 12초 동안
  • 2초 기계 → 6개
  • 3초 기계 → 4개
  • 7초 기계 → 1개
• 총 11개 ≥ 10개 → 가능

✍️ 한 줄 정리

이분 탐색은 값을 직접 찾는 게 아니라, "가능한지”를 기준으로 정답 범위를 줄여가는 알고리즘